package com.lwt.codetop.binaryTree;
// 124. 二叉树中的最大路径和

/**
 * 思路：二叉树的最大高度扩展版：
 *      要求root的最大路径和 = left + right + root.val
 *      我们递归返回左/右子树的最大路径和（一边）
 *      注意：由于存在负数，如果和小于0，我们就不要了，子树和就去0即可
 */
public class BinaryTreeMaximumPathSum {
    private static int res = -0x3f3f3f3f;
    public static void main(String[] args) {
        // 构建测试用例
        TreeNode root = new TreeNode(-10);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        //
        dfs(root);
        System.out.println(res);
    }

    /**
     * 后续遍历：递归获取树的最大（一边的最大高度/和）--> left、right
     * 更新res
     * @param root
     * @return
     */
    private static int dfs(TreeNode root){
        if (root == null) return 0;
        int left = Math.max(0, dfs(root.left));
        int right = Math.max(0, dfs(root.right));
        // 更新答案
        res = Math.max(res, left + right + root.val);
        // 返回最大和（高度）
        return Math.max(left, right) + root.val;
    }
}
